题解 P5834@洛谷 【[USACO19DEC]MooBuzz】

题目大意:求从一开始第nn个既不是三的倍数又不是五的倍数的数

没有思路。列几个数看看:

1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, ……

因为三乘五等于十五,所以猜测模15的余数可能有规律。列一下:

1, 2, 4, 7, 8, 11, 13, 14, 1, 2, 4, 7, 8, 11, 13, 14, ……

于是很明显地发现存在8位的循环节。根据数学推导可得(以下所有公式中的除号“/”均表示整除,即向下取整):

ans=(n/8)15+a[nmod8]ans=(n/8)*15+a[n\mod8],其中a[1...n]={14,1,2,4,7,8,11,13}a[1...n]=\{14, 1, 2, 4, 7, 8, 11, 13\},就是上面推导的余数。

但是当nmod8=0n\mod8=0时发现有问题,此时ans=(n/8)151ans=(n/8)*15-1,特判一下就好。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int a[8] = {14, 1, 2, 4, 7, 8, 11, 13};

int main()
{
	int n;
    cin>>n;
    int d = n / 8;
    int ans = d * 15;
    if(n % 8 != 0) ans += a[n%8];
    else --ans;
    cout<<ans<<endl;
    return 0;
}